#include <stdio.h>
#include <string.h>

// 获取next数组的下标
void Getnext(int* next, char* sub)
{
	// 先设置前两个next数组下标为 0 和 1
	next[0] = -1;
	//next[1] = 1;
	int i = 0;  // 开始填写next的位置
	int k = -1;  // k值开始的位置
	int length = strlen(sub);
	while (i < length)
	{
		// 判断的是 i 位置和下标为 k 位置处的字符是否相等
		// 不相等的话 k 值就一直往后退
		// 当走到 0 位置时就说明走到头 就结束
		if (k == -1 || sub[i] == sub[k])
		{
			++k;
			++i;
			next[i] = k;
		}
		else
		{
			k = next[k];
		}
	}
}

// 获取next数组的下标
void Get_valnext(int* valnext, char* sub)
{
	// 先设置前两个next数组下标为 0 和 1
	valnext[0] = -1;
	//next[1] = 1;
	int i = 0;  // 开始填写next的位置
	int k = -1;  // k值开始的位置
	int length = strlen(sub);
	while (i < length)
	{
		// 判断的是 i 位置和下标为 k 位置处的字符是否相等
		// 不相等的话 k 值就一直往后退
		// 当走到 0 位置时就说明走到头 就结束
		if (k == -1 || sub[i] == sub[k])
		{
			++k;
			++i;
			// 加上两个判断条件 相同的字符就回到相同的位置 减少重复字符出现的消耗
			if (sub[i] == sub[k])
				valnext[i] = valnext[k];
			else
				valnext[i] = k;
		}
		else
		{
			k = valnext[k];
		}
	}
}

// KMP 算法 cmp 字符串数组不往后退 一直往前比较
int KMP(int* next, char* cmp, char* sub, int pos)
{
	int cmplen = strlen(cmp);
	int sublen = strlen(sub);
	int i = pos;
	int j = 0;
	// 截至条件 i 或者 j 越界
	while (i < cmplen && j < sublen)
	{
		// 如果这个位置的字符相等 就继续往后走
		if (j == -1 || cmp[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			// 不符合条件 j 就退到 next数组下标的位置 i 的位置不变
			j = next[j];
		}
	}
	if (j == sublen)
		return i - j;
	return -1;
}

int main()
{
	char cmp[] = "ababcabcfabcde";
	char sub[] = "abcab";
	int next[6];
	//Getnext(next, sub);
	Get_valnext(next, sub);

	/*for (int i = 0; i < 6; i++)
	{
		printf("%d ", next[i]);
	}*/

	printf("%d\n", KMP(next, cmp, sub, 0));
	return 0;
}